﻿

//文件压缩项目—huffman树压缩

//1.大概思路：
//压缩：对于文件中的字符，使用空间占用更小的二进制编码来进行替换，字符的编码通过统计字符出现的频率，生成对应的哈夫曼树来生成。
//解压：在压缩文件中存入字符频次信息，以便于解压时生成对应哈夫曼树，已知字符编码，通过哈夫曼树的遍历来得到对应的字符。

//2.具体设计
// 
// 压缩
//1.设计FileGetCh()函数获取逐个字节获取文件中的字节获取信息来用于初始化ByteInfo结构体数组
//2.设计一个哈夫曼树类，使用处理过的字节类数组处理成字节，随后建立相关哈夫曼树，获得字符对应编码存入字节类对象数组
//3.新建文件，用于存入编码
//
//解压缩
//1.读入压缩文件中存入的频次信息，使用信息构建哈夫曼树
//2.新建文件，读入压缩文件中的编码数据，使用编码数据对哈夫曼树进行递归，获得解码后的字符，放入新建文件中

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>

using std::endl;
using std::cout;
using std::cin;

typedef unsigned char unchar;

struct ByteInfo {
	unchar _ch;
	int _times;
	std::string _chcode;
	ByteInfo(int times = 0)
		:_times(times)
	{
	}
	ByteInfo operator+ (const ByteInfo& x)const
	{
		return	ByteInfo(this->_times + x._times);
	}
	bool operator> (const ByteInfo& x)const
	{
		return _times > x._times;
	}
	bool operator== (const ByteInfo& x)const
	{
		return _times == x._times;
	}
	bool operator!= (const ByteInfo& x)const
	{
		return _times != x._times;
	}
};


//1.huffman树节点
template <class T>
struct HtNode
{
	HtNode<T>* _left;
	HtNode<T>* _right;
	HtNode<T>* _parent;
	T _chinfo;

	HtNode(const T& t=T())
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _chinfo(t)
	{
	}
};

//2.huffman树类
template <class T>
class huffman
{
	typedef HtNode<T> Node;

public:

	Node* _root;

	class cmp {
	public:
	bool operator() (const Node* x, const Node* y)const
	   {
	 		return x->_chinfo > y->_chinfo;
	   }
    };

	huffman()
		:_root(nullptr)
	{
	}

	/*friend bool operator< (const Node* N1, const Node* N2) {
		return N1->_weight > N2->_weight;
	}*/

	huffman(const std::vector<T>& bi,const T& invaild) //构造函数:传入数据类型为结构体ByteInfo类型的向量，取向量中的一个个数据即ByteInfo结构体初始化为一个个单独的节点，使用小堆结构对节点进行排序，构建哈夫曼树，
	{
		//使用优先级队列（小堆）来存储节点,自定义类型的数据存入优先级队列进行比较需要  1.运算符重载 或 2.仿函数重写  (使用仿函数重写)
		std::priority_queue<Node*, std::vector<Node*>, cmp> q;

		for (auto e:bi)
		{
			if(invaild!=e)
			  q.push(new Node(e));  //节点初始化，加入堆中
		}

		//构造哈夫曼树：使用优先级队列，获得最小节点，先创建左右子节点，再循环pop出最小节点构建树，直到队列中为空，最后创建的节点赋值给root节点
		//特殊情况：节点向量中只有一个节点

		if (q.size()==1)
		{
			_root = q.top();
			q.pop();
		}

		while (q.size()>1)
		{
			//将优先级队列视为一个二叉树森林，每循环一次，在森林中取两个节点合成新的树放入森林，并且剔除已经参与过合成的树，循环往复，直到森林中只剩下一棵树，该树为哈夫曼树

			Node* left = q.top();
			q.pop();

			Node* right = q.top();
			q.pop();

			Node* parent = (new Node(left->_chinfo+ right->_chinfo));

			parent->_left = left;
			parent->_right = right;

			left->_parent = parent;
			right->_parent = parent;

			q.push(parent);
		}

		_root = q.top();

	}

	~huffman() {
		//销毁huffman类对象中的资源
		Destory(_root);;
	}

private:

	void Destory(Node* root) {
		if (root)
		{
			Destory(root->_left);
			Destory(root->_right);
			delete root;

			root = nullptr;
		}
	}
};











